|
In data structures, a range query consists of preprocessing some input data into a data structure to efficiently answer any number of queries on any subset of the input. Particularly, there is a group of problems that have been extensively studied where the input is an array of unsorted numbers and a query consists in computing some function on a specific range of the array. In this article we describe some of these problems together with their solutions. ==Problem statement== We may state the problem of range queries in the following way: a range query on an array of ''n'' elements of some set , denoted , takes two indices , a function defined over arrays of elements of and outputs . This should be done space and time efficient. consider for instance and an array of numbers, the range query computes , for any . These queries may be answered in constant time and using extra space by calculating the sums of the first elements of and storing them into an auxiliar array , such that contains the sum of the first elements of for every .Therefore any query might be answered by doing . This strategy may be extended for every group operator where the notion of is well defined and easily computable. Finally notice this solution might be extended for arrays of dimension two with a similar preprocessing. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Range query (data structures)」の詳細全文を読む スポンサード リンク
|